package com.lx.algorithm.monotoneStack;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-08 10:24:18
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-08     张李鑫                     1.0         1.0 Version
 */

// 测试链接：https://leetcode-cn.com/problems/maximal-rectangle/
public class MaximalRectangle {
    /**
     * 给定一个二维数组matrix，其中的值不是0就是1，
     * 返回全部由1组成的最大子矩形，内部有多少个1
     */


    public static int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int[] arr = new int[matrix[0].length];
        MyStack myStack = new MyStack(arr);
        int max = Integer.MIN_VALUE;
        int[] tempArr = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int i1 = 0; i1 < matrix[i].length; i1++) {
                tempArr[i1] = matrix[i][i1] == '0' ? 0 : tempArr[i1] + 1;
            }
            max = Math.max(maxRecFromBottom(tempArr, myStack), max);
        }
        return max;
    }

    public static int maxRecFromBottom(int[] tempArr, MyStack myStack) {
        int max = Integer.MIN_VALUE;
        for (int i1 = 0; i1 < tempArr.length; i1++) {
            while (!myStack.isEmpty() && tempArr[myStack.peek()] > tempArr[i1]) {
                int pop = myStack.pop();
                int left = myStack.isEmpty() ? -1 : myStack.peek();
                max = Math.max(max, (i1 - left - 1) * (tempArr[pop]));
            }
            myStack.push(i1);
        }
        while (!myStack.isEmpty()) {
            int pop = myStack.pop();
            int left = myStack.isEmpty() ? -1 : myStack.peek();
            max = Math.max(max, (tempArr.length - 1 - left) * (tempArr[pop]));
        }
        return max;
    }


    //实现一个简易的栈 提高性能
    public static class MyStack {
        int[] arr;
        int start;

        public MyStack(int[] arr) {
            this.arr = arr;
            start = -1;
        }

        public int peek() {
            return arr[start];
        }

        public boolean isEmpty() {
            return start == -1;
        }

        public int pop() {
            return arr[start--];
        }

        public void push(int val) {
            arr[++start] = val;
        }
    }

    public static void main(String[] args) {
        char[][] arr = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}
        };
        System.out.println(maximalRectangle(arr));
    }

}
